package com.zjsru.oneDay202211;

/**
 * @Author: CookLee
 * @Date: 2022/11/28
 * 最大平均值和的分组
 *
 * 输入: nums = [9,1,2,3,9], k = 3
 * 输出: 20.00000
 * 解释:
 * nums 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
 * 我们也可以把 nums 分成[9, 1], [2], [3, 9].
 * 这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
 *
 * 输入: nums = [1,2,3,4,5,6,7], k = 4
 * 输出: 20.50000
 *
 */
public class LargestSumOfAverages {
    
    /**
     * DP
     */
    public double largestSumOfAverages(int[] nums, int k) {
        int len = nums.length;
        double[] sum = new double[len + 1];
        for (int i = 1; i <= len; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        double[][] f = new double[len + 1][len + 1];
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= Math.min(i, k); j++) {
                if (j == 1) {
                    f[i][1] = sum[i] / i;
                } else {
                    for (int l = 2; l <= i; l++) {
                        f[i][j] = Math.max(f[i][j], f[l - 1][j - 1] + (sum[i] - sum[l - 1]) / (i - l + 1));
                    }
                }
            }
        }
        return f[len][k];
    }
    
    public static void main(String[] args) {
        LargestSumOfAverages largestSumOfAverages = new LargestSumOfAverages();
        int[] nums = new int[] {9, 1, 2, 3, 9};
        int k = 3;
        System.out.println(largestSumOfAverages.largestSumOfAverages(nums, k));
    }
}
